package com.example.linked.skiplist;

public class Leetcode1206_SkipList {

    /**
     * 跳表其实是一个用空间换时间的数据结构
     * 功能和性能与树堆、红黑树相当，却比后者好理解，代码更少
     * 使用链表实现
     * <p>
     * 跳表特点：
     * 跳表的每一层都是链表
     * 由很多层有序的链表结构组成
     * 最底层（Level 1）称为原链表，包含所有元素
     * 上面每一层（Level i）链表都叫索引层，上级索引是下一级的子集
     * 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现
     * <p>
     * 实现整体步骤:
     * 1.先实现一个插入删除不考虑索引的跳表
     * <p>
     * 2.实现有索引的插入和删除
     */

    public static void main(String[] args) {
//        SkiplistNoIndex skiplist = new SkiplistNoIndex();
        Skiplist skiplist = new Skiplist();


        skiplist.add(1);
        skiplist.add(2);
        skiplist.add(3);
        System.out.println(skiplist.search(0));
        skiplist.add(4);
        System.out.println(skiplist.size);
        System.out.println(skiplist.search(1));
        System.out.println(skiplist.erase(0));
        System.out.println(skiplist.size);
        System.out.println(skiplist.erase(2));
        System.out.println(skiplist.search(1));
        System.out.println(skiplist.search(4));
        System.out.println(skiplist.size);

    }


}
